package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * (C卷,200分)- 机器人走迷宫（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 房间由XY的方格组成，例如下图为6*4的大小。每一个方格以坐标(x，y)描述。
 * 机器人固定从方格(0，0)出发，只能向东或者向北前进。出口固定为房间的最东北角，如下图的方格(5，3)。用例保证机器人可以从入口走到出口。
 * 房间有些方格是墙壁，如(4，1)，机器人不能经过那儿。
 * 有些地方是一旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格。
 * 有些地方是机器人无法到达的的，如标记为A的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。
 * 如下示例图中，陷阱方格有2个，不可达方格有3个。
 * 请为该机器人实现路径规划功能：给定房间大小、墙壁位置，请计算出陷阱方格与不可达方格分别有多少个。
 * <p>
 * <p>
 * 输入描述
 * <p>
 * 第一行为房间的X和Y（0 < X,Y <= 1000）
 * 第二行为房间中墙壁的个数N（0 <= N < X*Y）
 * 接着下面会有N行墙壁的坐标
 * 同一行中如果有多个数据以一个空格隔开，用例保证所有的输入数据均合法。（结尾不带回车换行）
 * <p>
 * 输出描述
 * <p>
 * 陷阱方格与不可达方格数量，两个信息在一行中输出，以一个空格隔开。（结尾不带回车换行）
 * <p>
 * 用例
 * <p>
 * 输入
 * <p>
 * 6 4
 * <p>
 * 5
 * <p>
 * 0 2
 * <p>
 * 1 2
 * <p>
 * 2 2
 * <p>
 * 4 1
 * <p>
 * 5 1
 * <p>
 * 输出	2 3
 * 说明	该输入对应上图示例中的迷宫，陷阱方格有2个，不可达方格有3个
 * <p>
 * 输入
 * <p>
 * 6 4
 * <p>
 * 4
 * <p>
 * 2 0
 * <p>
 * 2 1
 * <p>
 * 3 0
 * <p>
 * 3 1
 * <p>
 * 输出	0 4
 * 说明
 * 该输入对应的迷宫如下图，没有陷阱方格，不可达方格有4个，分别是(4,0) (4,1) (5,0) (5,1)
 */
public class DFSRobotsNavigateMazes {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        x = sc.nextInt(); // 行数
        y = sc.nextInt(); // 列数
        n = sc.nextInt(); // 墙数

        poses = new int[n][2]; // 墙位置
        for (int i = 0; i < n; i++) {
            poses[i][0] = sc.nextInt();
            poses[i][1] = sc.nextInt();
        }*/

        String input1 = "6 4";
        int[] input1Arr = Arrays.stream(input1.split(" ")).mapToInt(Integer::parseInt).toArray();
        int x = input1Arr[0]; // 行数
        int y = input1Arr[1]; // 列数
        int n = 5; // 墙数
        String input2 = "0 2\n1 2\n2 2\n4 1\n5 1";
        int[][] poses = Arrays.stream(input2.split("\n")).
                map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(poses, x, y));
    }

    public static String getResult(int[][] poses, int x, int y) {
        int[][] matrix = new int[x][y];

        for (int[] pos : poses) {
            int i = pos[0];
            int j = pos[1];
            matrix[i][j] = 1; // 墙点值为1，非墙点值为0
        }

        matrix[x - 1][y - 1] = 2; // 可达点值为2

        dfs(matrix, 0, 0, x, y);

        // 陷阱数量
        long unreach = Arrays.stream(matrix)
                .flatMapToInt(IntStream::of)
                .filter(i -> i == 0)
                .count();

        // 不可达点数量
        long trap = Arrays.stream(matrix)
                .flatMapToInt(IntStream::of)
                .filter(i -> i == -1)
                .count();

        return trap + " " + unreach;
    }

    public static boolean dfs(int[][] matrix, int cx, int cy, int x, int y) {
        if (cx >= x || cy >= y) {
            return false;
        }
        if (matrix[cx][cy] == 1) {
            return false;
        }
        if (matrix[cx][cy] == -1) {
            return false;
        }
        if (matrix[cx][cy] == 2) {
            return true;
        }

        if (matrix[cx][cy] == 0) {
            boolean east = dfs(matrix, cx + 1, cy, x, y);
            boolean north = dfs(matrix, cx, cy + 1, x, y);

            if (east || north) {
                matrix[cx][cy] = 2; // 如果向东可达或者向北可达，则当前点可达，将值设为2
            } else {
                matrix[cx][cy] = -1; // 如果向东，向北都不可达，则当前点也是不可达点，将值设为-1
            }
        }

        return matrix[cx][cy] == 2;
    }
}